#include <iostream>
#include <vector>
#include <string>
#include <cctype>

// turn integer[0, 15] to a 4 bits binary number
const std::vector<int> &decimalToBinary(int dec)
{
	static std::vector<int> ret(4);

	for (std::vector<int>::size_type i = 0; i != 4; ++i)
	{
		ret[i] = ((dec >> (3 - i)) & 0x01);
	}

	return ret;
}

// turn character['0', 'F'] to integer[0, 15]
inline int charToDecimal(char ch)
{
	return (std::isalpha(ch) ? ch - 'A' + 10 : ch - '0');
}

void binayToReversedOctal(const std::vector<int> &input, std::vector<int>& output)
{
	static int octalValue[] = {0, 0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 6, 1, 5, 3, 7};

	output.clear();

	std::string::size_type inputIndex = input.size();

	int octalValueIndex, i;
	while (inputIndex)
	{
		for (octalValueIndex = 1, i = 0; i < 3 && inputIndex; ++i, --inputIndex)
		{
			octalValueIndex <<= 1;

			if (input[inputIndex - 1])
				++octalValueIndex;
		}
		output.push_back(octalValue[octalValueIndex]);
	}

	while (output.size() > 1U && !output.back())
		output.pop_back();
}

int main()
{
	std::string line;
	int lineCount;

	std::cin >> lineCount;
	std::cin.get();

	std::vector<int> bin;	// binary number
	std::vector<int> roct;	// reversed octal number
	while (lineCount--)
	{
		std::getline(std::cin, line);
		for (std::string::size_type i = 0; i < line.size(); ++i)
		{
			// get 4 bits binary number from each character
			const std::vector<int> &bin4b = decimalToBinary(charToDecimal(line[i]));
			bin.insert(bin.end(), bin4b.begin(), bin4b.end());
		}

		binayToReversedOctal(bin, roct);

		for (std::vector<int>::size_type i = roct.size(); i ; --i)
			std::cout.put(roct[i - 1] + '0');
		std::cout.put('\n');

		bin.clear();
	}

	return 0;
}